package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-09
 * Description
 *
 *
 * 状态转移方程为：
 * dp[n] = max(dp[n-1], dp[n - 2] + num[n])
 *
 * https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-dong-tai-gui-hua-jie-gou-hua-si-lu-/
 *
 *
 */
public class Solution35 {
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);// 从第一家和第二家中挑选出最大的值。
        for (int i = 2; i < length ; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[length - 1];
    }

    public static int rob2(int[] nums) {
        int pre = 0, cur = 0, tmp;
        for (int num : nums) {
            tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }

    public static void main(String[] args) {
        int[] array = {2, 7, 9, 3, 1};
        int rob = rob(array);
        System.out.println(rob);
    }
}
